Viterbi decoders are used at a receiver to decode a data bit stream that has been encoded with a convolutional code for forward error correction (FEC). Viterbi decoders use the Viterbi algorithm which finds the most likely sequence of hidden states, e.g., states of a hidden Markov model (Forney, G. D., Jr.; “The Viterbi algorithm,” Proceedings of the IEEE, vol. 61, No. 3, pp. 268-278, March 1973). For example, when a radio frequency (RF) signal is received for decoding, the originally transmitted signal is unknown to the receiver. In addition, the originally transmitted signal may have been changed by the radio channel characteristics such as noise, fading, rain showers, etc. Accordingly, the originally transmitted signal bits are a “hidden” or unknown. FEC and Viterbi decoders are desirable when error correction is to be performed at the receiver or when feedback from the receiver to the transmitter is not practical. Viterbi decoders find practical uses in wireless communications, e.g., cellular telephone and satellite communications, speech recognition, storage verification, among others. This is the case in the 3rd Generation Partnership Project (3GPP) Long Term Evolution (LTE) cellular communication system where a convolutional code is used to improve the decoding reliability of the control channels (3GPP Technical Specification (TS) 36.212).
When used in wireless communications the receiver has a detector that generates an output signal that is fed into a Viterbi decoder. The decoder has to decide if the transmitted bits are ones or zeros. The input to the decoder from the detector may be in a binary form, which is known as a “hard” decision, or in the form of probability value, which is known as a “soft” decision. Hard decisions are made using signal strength comparison while soft decisions may be made with a probabilistic model.
The Viterbi decoder generates a Maximum Likelihood Sequence Estimate (MLSE) of the transmitted bits by keeping track of the most likely path in the trellis associated with the convolutional code for each possible state. These most likely paths are also referred to as survivor sequences and are used to generate the decoded bit sequence. Two different approaches can be used for the generation of these sequences, register-exchange method and a trace-back method (Feygin, G.; Gulak, P.; “Architectural tradeoffs for survivor sequence memory management in Viterbi decoders,” IEEE Transactions on Communications, vol. 41, no. 3, pp. 425-429, March 1993). The register-exchange method is conceptually simpler but leads to a larger number of memory accesses than the trace-back approach. The trace-back approach is therefore usually selected for implementation.
In order to help with the Viterbi decoding process, the convolutional code encoder state is often populated with 0 values. This forces the starting state in the Viterbi trellis processing to be equal to 0 and can be used to initialize the path metrics associated with the different states. Similarly, the encoder final state is often forced to 0 by appending a number of 0 bits to the end of the message. Forcing the final encoder state to 0 can lead to an improved performance as the decoder can make use of this information to decide on which survivor sequence to use for the generation of the decoded bits. The number of extra bits needed to force the final encoder state is equal to the memory or constraint length of the encoder. In other words the encoder is “flushed” with zeroes. Convolutional codes that flush the encoder with known values are known as “tailed” convolutional codes.
This performance improvement from tailed convolutional codes comes at the cost of reduced spectral efficiency since extra bits need to be added to the information message. Hence, when the information message length is large compared to the encoder memory, the spectral efficiency penalty is small and can be ignored. On the other hand, when transmitting short messages, the penalty can be significant and forcing the final encoder state to 0 (or any other fixed value) should be avoided. The spectral efficiency penalty can be avoided by using a “tail-biting” convolutional code (Ma, H.; Wolf, J.; “On Tail Biting Convolutional Codes,” IEEE Transactions on Communications, vol. 34, no. 2, pp. 104-111, February 1986). Tail-biting convolutional codes do not force the initial and final states of the encoder to a known value but instead guarantee that they are both identical. This is achieved without any penalty on the spectral efficiently by initializing the state of the encoder with the final bits in the message to be transmitted.
Tail-biting convolutional codes offer performance similar to that of tailed convolutional code and do not suffer from any spectral efficiency loss. As a result of these properties, these convolutional codes are now often used for the coding and transmission of short information messages. They are, for example, used to protect some of the control channels, e.g., the physical broadcast channel (PBCH) or the physical downlink control channel (PDCCH) defined in 3GPP LTE.
It should however be noted that tail-biting convolutional codes have a higher decoding complexity. The Maximum Likelihood Detector (MLD) for a tail-biting convolutional code requires S separate Viterbi decoding operations of the whole received sequence, each hypothesized on the initial and final states of the encoder, where S represents the total number of states in the trellis associated with the convolutional code. The best path across these S different possibilities would then provide the decoded bits (Shao, R. Y.; Shu Lin; Fossorier, M. P. C.; “Two Decoding Algorithms for Tailbiting Codes,” IEEE Transactions on Communications, vol. 51, no. 10, pp. 1658-1665, October 2003). A number of sub-optimum decoding algorithms have also been proposed in order to achieve near MLD performance but with a reduced complexity (Cox, R. V.; Sundberg, C. E. W.; “An Efficient Adaptive Circular Viterbi Algorithm for Decoding Generalized Tailbiting Convolutional Codes,” IEEE Transactions on Vehicular Technology, vol. 3, no. 1, pp. 57-68, February 1994; and Zhang Min; Huang Junwei; Meng Jie; Deng Qiang; “Research on An-Based Decode of Tail-Biting Convolutional Codes and Their Performance Analyses Used in LTE System,” 2009 International Forum on Information Technology and Applications, IFITA '09, vol. 2, pp. 303-306, 15-17 May 2009).